package puzzle.nurikabe.solver;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import puzzle.common.data.HatanException;
import puzzle.common.point.Direction;
import puzzle.common.point.Pnt;
import puzzle.common.solver.AbstractSolver;
import puzzle.common.solver.BoardSnapshot;
import puzzle.common.solver.SolutionState;
import puzzle.nurikabe.data.NurikabeBoard;
import puzzle.nurikabe.data.ShimaState;

public class NurikabeSolver extends
		AbstractSolver<NurikabeBoard, NurikabeTopology, NurikabeAssumption> {

	public NurikabeSolver() {
//		addRule(new ShimaIsolationRule());
		addRule(new ShimaBorderRule());
		addRule(new AvoidCrusterRule());
		addRule(new BoardwiseShimaPotentialRule());
		addRule(new ShimawiseShimaPotentialRule());

//		addTopologicalRule(new TopologicalRuleAdaptor<NurikabeBoard, NurikabeTopology>(
//				new BoardwiseShimaPotentialRule()));
//		addTopologicalRule(new TopologicalRuleAdaptor<NurikabeBoard, NurikabeTopology>(
//				new ShimawiseShimaPotentialRule()));

		addTopologicalRule(new NeutralClosureRule());
		addTopologicalRule(new ShimaEscapeRule());
		addTopologicalRule(new KabeEscapeRule());
	}

	@Override
	protected NurikabeTopology analyzeTopology(NurikabeBoard b) {
		return new NurikabeTopology(b);
	}

	@Override
	protected SolutionState checkSolutionState(NurikabeBoard b, NurikabeTopology topology) {
		boolean isComplete = true;

		for (ShimaState s : b.getShimaStates()) {
			if (s.getArea() > s.n) {
				return SolutionState.HATAN;
			} else if (s.getArea() < s.n) {
				isComplete = false;
			}
		}

		if (topology.getKabeEscapePoints().size() != 1) {
			isComplete = false;
		}

		if (topology.getUndecidedArea() > 0) {
			isComplete = false;
		}

		return isComplete ? SolutionState.COMPLETE : SolutionState.INCOMPLETE;
	}

	@Override
	protected List<NurikabeAssumption> assume(NurikabeBoard b, NurikabeTopology topology,
			NurikabeAssumption prevAssumption) {
		List<NurikabeAssumption> result = new ArrayList<NurikabeAssumption>();

		List<PntEntry> entries = new ArrayList<PntEntry>();

		for (List<Pnt> ps : topology.getShimaEscapePoints().values()) {
			for (Pnt p : ps) {
				addPntEntry(entries, b, topology, p, prevAssumption);
			}
		}

		Collections.sort(entries, PntEntry.COMPARATOR);

		for (PntEntry e : entries) {
			if (e.kabeCellsAround > 0) {
				result.add(new NurikabeAssumption(e.p, true));
			}
			if (e.shimaCellsAround > 0) {
				result.add(new NurikabeAssumption(e.p, false));
			}
		}

		return result;
	}

	private void addPntEntry(List<PntEntry> entries, NurikabeBoard b, NurikabeTopology topology,
			Pnt p, NurikabeAssumption prevAssumption) {
		for (PntEntry e : entries) {
			if (e.p.equals(p)) {
				// the specified point already exists
				return;
			}
		}

		int kabeCellsAround = 0;
		int shimaCellsAround = 0;
		double escapeFactor = 0;
		for (Direction d : Direction.CLOCKWISE8) {
			int n = b.getBoardState(p.x + d.v.dx, p.y + d.v.dy);
			if (n < 0) {
				kabeCellsAround++;
			} else if (n > 0) {
				shimaCellsAround++;
				escapeFactor += 1.0 / topology.getShimaEscapePoints().get(n).size();
			}
		}

		escapeFactor /= shimaCellsAround;

		entries.add(new PntEntry(p, shimaCellsAround, kabeCellsAround, escapeFactor));

	}

	private static class PntEntry {
		public final Pnt p;
		public final int shimaCellsAround;
		public final int kabeCellsAround;
		public final int fixedCellsAround;
		public final double escapeFactor;

		public PntEntry(Pnt p, int shimaCellsAround, int kabeCellsAround, double escapeFactor) {
			this.p = p;
			this.shimaCellsAround = shimaCellsAround;
			this.kabeCellsAround = kabeCellsAround;
			this.fixedCellsAround = shimaCellsAround + kabeCellsAround;
			this.escapeFactor = escapeFactor;
		}

		public static final Comparator<PntEntry> COMPARATOR = new Comparator<PntEntry>() {
			public int compare(PntEntry o1, PntEntry o2) {
				if (o1.fixedCellsAround > o2.fixedCellsAround) {
					return -1;
				} else if (o1.fixedCellsAround < o2.fixedCellsAround) {
					return 1;
				}

				if (o1.escapeFactor > o2.escapeFactor) {
					return -1;
				} else if (o1.escapeFactor < o2.escapeFactor) {
					return 1;
				}

				return 0;
			}
		};
	}

	@Override
	protected void applyAssumption(
			List<BoardSnapshot<NurikabeBoard, NurikabeTopology, NurikabeAssumption>> bss,
			NurikabeBoard b, NurikabeAssumption a) throws HatanException {
		if (a.isKabe) {
			b.setKabe(a.p.x, a.p.y);
		} else {
			b.setShima(a.p.x, a.p.y);
		}

		b.setAssumed(a.p.x, a.p.y);
	}

	@Override
	protected void excludeAssumption(NurikabeBoard b, NurikabeAssumption a) throws HatanException {
		if (!a.isKabe) {
			b.setKabe(a.p.x, a.p.y);
		} else {
			b.setShima(a.p.x, a.p.y);
		}
	}

	@Override
	protected boolean isAlreadyTried(
			List<BoardSnapshot<NurikabeBoard, NurikabeTopology, NurikabeAssumption>> bss,
			NurikabeBoard b, NurikabeAssumption a) {
		if (b.getBoardState(a.p.x, a.p.y) != 0) {
			return true;
		}

		for (BoardSnapshot<NurikabeBoard, NurikabeTopology, NurikabeAssumption> bs : bss) {
			NurikabeBoard b1 = bs.getBoard();
			int n1 = b1.getBoardState(a.p.x, a.p.y);
			if ((n1 > 0 && !a.isKabe) || (n1 < 0 && a.isKabe)) {
				return true;
			}
		}

		return false;
	}

	@Override
	protected void sortBoardSnapshots(
			List<BoardSnapshot<NurikabeBoard, NurikabeTopology, NurikabeAssumption>> bss) {
		Collections.sort(bss, BOARD_COMPARATOR);
	}

	private static final Comparator<BoardSnapshot<NurikabeBoard, NurikabeTopology, NurikabeAssumption>> BOARD_COMPARATOR = new Comparator<BoardSnapshot<NurikabeBoard, NurikabeTopology, NurikabeAssumption>>() {
		public int compare(BoardSnapshot<NurikabeBoard, NurikabeTopology, NurikabeAssumption> o1,
				BoardSnapshot<NurikabeBoard, NurikabeTopology, NurikabeAssumption> o2) {
			return o2.getTopology().getFixedArea() - o1.getTopology().getFixedArea();
		}
	};

}
